package com.liouxb.data.structure.queue;

/**
 * 环形队列
 * 数组实现
 *
 * @author liouwb
 */
public class QueueCircleDemo {
    public static void main(String[] args) {

    }
}

/**
 * 使用数组实现环形队列
 */
class CircleArrayQueue {
    // 队列(集合)的最大长度
    private int maxSize;

    // 队列头
    private int front;

    // 队列尾
    private int rear;

    // 数据集合
    private int[] arrQueue;

    /**
     * 构造函数
     */
    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arrQueue = new int[maxSize];
        // 指向队列头数据的第一个元素的位置
        this.front = 0;
        // 最后一个元素的后一个位置
        this.rear = 0;
    }

    /**
     * 环形队列判断是否已满
     *
     * @return
     */
    boolean isFull() {
        return (this.rear + 1) / this.maxSize == this.front;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty() {
        return this.rear == this.front;
    }

    /**
     * 向队列中添加数据
     */
    void addQueue(int param) {

        // 1、判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，请等待。。。");
        }

        arrQueue[rear] = param;

        // 尾部向后移
        this.rear = (rear + 1) % maxSize;


    }

    /**
     * 从队列中获取数据
     */
    int popQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        // 1、用一个临时变量保存要取的元素
        // 2、front后移
        // 3、返回临时变量
        int temp = 0;
        temp = this.arrQueue[front];

        // 头部后移
        this.front = (this.front + 1) / maxSize;

        return temp;
    }

    /**
     * 获取队列所有数据
     */
    void showAllQueue() {

        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }

        // 从front开始遍历：需要遍历有效数据个数
        int count = count();

        for (int i = front; i < front + count; i++) {

            System.out.println(arrQueue[i]);
        }

    }

    /**
     * 获取环形队列有效元素个数
     * (rear+maxSize-front)%maxSize
     *
     * @return
     */
    private int count() {
        return (rear + maxSize - front) % maxSize;
    }
}